//
// Created by Xu Xiao on 2022/9/30.
//

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <unordered_map>
#include "EulerSieve.h"

#ifndef ALGORITHM_22_1_SOLUTION0930_H
#define ALGORITHM_22_1_SOLUTION0930_H

using namespace std;


class Solution0930 {
public:
    static void A_Q2570() {
        int n;
        auto t = EulerSieve::getPrimeAndIsPrimeTable(1000005);
        auto prime = t.first;
        auto isPrime = t.second;
        while (cin >> n, n != 0) {
            for (int i = 1; i <= n; i++) {
                auto x = prime[i];
                if (isPrime[n - x]) {
                    printf("%d = %d +%d\n", n, x, n - x);
                    break;
                }
            }
        }
        delete[] prime;
        delete[] isPrime;
    }

    static void B_Q2571() {
        int n, i, j, k;
        auto t = EulerSieve::getPrimeAndIsPrimeTable(10000005);
        auto prime = t.first;
        auto isPrime = t.second;
        while (cin >> n) {
            if (n < 8) {
                printf("Impossible.\n");
                continue;
            }
            string str;
            if (n % 2 == 0) {
                str = "2 2 ";
                n -= 4;
            } else {
                str = "2 3 ";
                n -= 5;
            }
            int num = prime[0];
            for (i = 1; i <= num; i++) {
                if (prime[i] * 2 > n) {
                    printf("Impossible.\n");
                    break;
                }
                if (isPrime[n - prime[i]]) {
                    printf("%s", str.c_str());
                    printf("%d %d\n", prime[i], n - prime[i]);
                    break;
                }
            }
        }

        delete[] prime;
        delete[] isPrime;
    }

    static void C_Q2572() {
        auto t = EulerSieve::getPrimeAndIsPrimeTable(1000005);
        auto prime = t.first;
        auto isPrime = t.second;
        int n;
        int *dp = new int[1000005];
        for (int i = 2; i <= 1000000; i++) {
            if (!isPrime[i]) {
                dp[i] = dp[i - 1];
                continue;
            }
            string str = to_string(i);
            int sum = 0;
            for (char &c: str) {
                sum += c - '0';
            }
            if (!isPrime[sum]) {
                dp[i] = dp[i - 1];
                continue;
            }
            dp[i] = dp[i - 1] + 1;
        }
        cin >> n;
        int x, y;
        while (n--) {
            scanf("%d%d", &x, &y);
            printf("%d\n", dp[y] - dp[x - 1]);//必须是x-1，如[2,2]应为1个
        }
        delete[] dp;
        delete[] prime;
        delete[] isPrime;
    }

    static void D_Q2573() {
        auto t = EulerSieve::getPrimeAndIsPrimeTable(1300005);
        auto prime = t.first;
        auto isPrime = t.second;
        int *ans = new int[1300005]{};
        for (int i = 2; i <= 1299709;) {
            int x = i + 1;
            while (!isPrime[x]) x++;
            int gap = x - i;
            for (int j = i + 1; j < x; j++) {
                ans[j] = gap;
            }
            i = x;
            ans[i] = 0;
        }

        int n;
        while (scanf("%d", &n), n != 0) {
            printf("%d\n", ans[n]);
        }
        delete[] ans;
        delete[] prime;
        delete[] isPrime;
    }

    static void E_Q2574() {
        auto p = EulerSieve::getPrimeAndIsPrimeTable(1300005);
        auto prime = p.first;
        auto isPrime = p.second;
        int t;
        scanf("%d", &t);
        while (t--) {
            int n;
            scanf("%d", &n);
            int *arr = new int[n + 10];
            int *dp = new int[n + 10];
            for (int i = 0; i < n; i++) {
                scanf("%d", &arr[i]);
            }
            for (int i = 1; i < n + 1; i++) {
                dp[i] = dp[i - 1] + arr[i - 1];
            }
            int m = INT_MAX;
            int x, y;
            for (int i = 0; i < n - 1; i++) {
                for (int j = i + 1; j < n; j++) {
                    if (isPrime[dp[j + 1] - dp[i]]) {
                        int _m = j - i + 1;
                        if (_m < m) {
                            m = _m;
                            x = i;
                            y = j;
//                            printf("dpi:%d dpj:%d m:%d x:%d y:%d\n", dp[i], dp[j], m, x, y);
                        }
                    }
                }
            }
            if (m < INT_MAX) {
                printf("Shortest primed subsequence is length %d:", m);
                for (int i = x; i <= y; i++) {
                    printf(" %d", arr[i]);
                }
                printf("\n");
            } else {
                printf("This sequence is anti-primed.\n");
            }

            delete[] arr;
            delete[] dp;
        }
        delete[] prime;
        delete[] isPrime;
    }

};


#endif //ALGORITHM_22_1_SOLUTION0930_H
